// 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
// nums = [1, 2, 3]
// target = 4
// 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
// 请注意，顺序不同的序列被视作不同的组合。
// 因此输出为 7

// 思路，动态规划
// 求排列，和上题的区别就在于遍历顺序，本题先外层遍历背包，内层遍历物品
function combinationSum4(nums, target) {
    let dp = new Array(target + 1).fill(0)
    dp[0] = 1
    for (let i = 1; i <= target; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i >= nums[j]) {
                dp[i] += dp[i - nums[j]]
            }            
        }        
    }
    return dp[target]
}

nums = [1, 2, 3]
target = 4
console.log(combinationSum4(nums, target))
